package org.example.algorithm.dp;

import java.util.Arrays;

public class MaxProfit3Solution {

    public static void main(String[] args) {
        MaxProfit3Solution solution = new MaxProfit3Solution();
        int[] prices = {3,5,1,4};
        int res = solution.maxProfit(prices);
        System.out.println(res);
    }

    //dp优化版
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int k = 2;
        int[][] dp = new int[k+1][2];
        for (int j=0;j<=k;j++) {
            dp[j][0] = 0;
            dp[j][1] = Integer.MIN_VALUE;
        }
        for (int i=0;i<len;i++) {
            for (int j=0;j<k;j++) {
                dp[j+1][1] = Math.max(dp[j+1][1], dp[j][0] - prices[i]);
                dp[j+1][0] = Math.max(dp[j+1][0], dp[j+1][1] + prices[i]);
            }
        }
        return dp[k][0];
    }

    //dp优化版
    public int maxProfit4(int[] prices) {
        int len = prices.length;
        int k = 2;
        int[][][] dp = new int[len+1][k+1][2];
        for (int j=0;j<=k;j++) {
            dp[0][j][0] = 0;
            dp[0][j][1] = Integer.MIN_VALUE;
        }
        for (int i=0;i<len;i++) {
            for (int j=0;j<k;j++) {
                dp[i+1][j+1][1] = Math.max(dp[i][j+1][1], dp[i][j][0] - prices[i]);
                dp[i+1][j+1][0] = Math.max(dp[i][j+1][0], dp[i][j+1][1] + prices[i]);
            }
        }
        return dp[len][k][0];
    }

    //dp
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int k = 2;
        int[][][] dp = new int[len+1][k*2+1][2];
        for (int j=0;j<k*2;j++) {
            dp[0][j][0] = 0;
            dp[0][j][1] = Integer.MIN_VALUE;
        }
        for (int i=0;i<len;i++) {
            for (int j=0;j<k*2;j++) {
                dp[i+1][j+1][1] = Math.max(dp[i][j+1][1], dp[i][j][0] - prices[i]);
                dp[i+1][j+1][0] = Math.max(dp[i][j+1][0], dp[i][j][1] + prices[i]);
            }
        }
        return dp[len][2*k][0];
    }

    //此解法超时
    public int maxProfit3(int[] prices) {
        int len = prices.length;
        int k = 2;
        int[][][] mem = new int[len][k*2][2];
        for (int i=0;i<len;i++) {
            for (int j=0;j<k*2;j++) {
                Arrays.fill(mem[i][j], -1);
            }
        }
        return dfs(prices, mem, len-1, 0, k*2-1);
    }

    private int dfs(int[] prices, int[][][] mem, int i, int hold, int k) {
        //无法继续买卖
        if (k < 0) {
            return 0;
        }
        if (i<0) {
            return hold == 0 ? 0 : Integer.MIN_VALUE;
        }
        if (mem[i][k][hold] != -1) {
            return mem[i][k][hold];
        }
        if (hold == 1) {
            //!!!重要，k为偶数时才可以买入
            if (k % 2 == 0) {
                return mem[i][k][hold] = Math.max(dfs(prices, mem, i-1, hold, k), dfs(prices, mem, i-1, 0, k-1) - prices[i]);
            } else {
                return mem[i][k][hold] = dfs(prices, mem, i-1, hold, k);
            }
        }
        //!!!重要，k为奇数时才可以卖出
        if (k % 2 != 0) {
            return mem[i][k][hold] = Math.max(dfs(prices, mem, i-1, 1, k-1) + prices[i], dfs(prices, mem, i-1, 0, k));
        } else {
            return mem[i][k][hold] = dfs(prices, mem, i-1, 0, k);
        }
    }

}
